#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <stdlib.h>


//int* twoSum(int* numbers, int numbersSize, int target, int* returnSize) {
//    int* ans = (int*)malloc(sizeof(int) * 2);
//    int left = 0;
//    int right = numbersSize - 1;
//    while (left < right)
//    {
//        if (numbers[left] + numbers[right] < target)
//            left++;
//        else if (numbers[left] + numbers[right] > target)
//            right--;
//        else
//        {
//            ans[0] = left + 1;
//            ans[1] = right + 1;
//            break;
//        }
//    }
//    *returnSize = 2;
// 
// 
// 
//    return ans;
//}


int cmp_int(const void* e1, const void* e2)
{
    return *(int*)e1 - *(int*)e2;
}
int** threeSum(int* nums, int numsSize, int* returnSize, int** returnColumnSizes) {
    qsort(nums, numsSize, sizeof(int), cmp_int);

    int base = 100;
    int** ans = (int**)malloc(sizeof(int*) * base);
    int ArrIndex = 0;

    int i = 0;
    int j = 0;
    int k = 0;
    int n = numsSize;
    int sum = 0;

    for (i = 1; i < n - 1; i++)
    {
        sum = nums[i - 1];
        if (nums[i] == nums[i - 1])
            continue;
        j = i;
        int target = 0 - sum;
        k = n - 1;
        while (j < k)
        {
            if (nums[j] + nums[k] < target)
                j++;
            else if (nums[j] + nums[k] > target)
                k--;
            else
            {
                int* arr = (int*)malloc(sizeof(int) * 3);
                arr[0] = sum;
                arr[1] = nums[j];
                arr[2] = nums[k];
                if (ArrIndex == base)
                {
                    base *= 2;
                    ans = (int**)realloc(ans, sizeof(int*) * base);
                }
                ans[ArrIndex++] = arr;
                j++;
                while (j < k && nums[j] == nums[j - 1])
                    j++;
                k--;
                while (j < k && nums[k] == nums[k + 1])
                    k--;
            }
        }
    }
    *returnColumnSizes = (int*)malloc(sizeof(int) * ArrIndex);
    for (i = 0; i < ArrIndex; i++)
    {
        (*returnColumnSizes)[i] = 3;
    }
    *returnSize = ArrIndex;
    return ans;
}

int main()
{
    int nums[] = { -1,0,1,2,-1,-4 };
    int target = 9;
    int sz = sizeof(nums) / sizeof(nums[0]);
    int size = 0;
    int** retcol = NULL;
    int* ret = threeSum(nums,sz,&size, retcol);
    return 0;
}